---
title: "平均"
created: 2025-11-28
tags:
  - 算法
---

# 平均

## 题目 [平均](https://www.acwing.com/problem/content/5398/)

![[image-4d08e3f1.png]]

## 思路分析

若n=10 就要让0-9全都出现一次 若n为20 就1-9全出现两次

贪心策略1：

由n/10可以确定出各个数应该出现的次数 令其为mid 只存在大于mid的补给小于mid的 不存在大于mid补给大于mid 小于mid补给小于mid
小于mid补给大于mid的情况 所以只需要考虑所有大于mid的数 它们的花费代价

贪心策略2：

更改不同的数 花费的代价不同 优先更改花费小的数

问题解决

## 代码实现

一开始不确定map能否嵌套优先队列 这代码给我写笑了

```cpp
#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int>> zero;

priority_queue<int,vector<int>,greater<int>> one;

priority_queue<int,vector<int>,greater<int>> two;

priority_queue<int,vector<int>,greater<int>> three;

priority_queue<int,vector<int>,greater<int>> four;

priority_queue<int,vector<int>,greater<int>> five;

priority_queue<int,vector<int>,greater<int>> six;

priority_queue<int,vector<int>,greater<int>> seven;

priority_queue<int,vector<int>,greater<int>> eight;

priority_queue<int,vector<int>,greater<int>> nine;

int main()

{

    int n;cin>>n;

    for(int i=0;i<n;i++){

        int a,b;cin>>a>>b;

        switch(a)

        {

            case 0:{

                zero.push(b);

                break;

            }

            case 1:{

                one.push(b);

                break;

            }

            case 2:{

                two.push(b);

                break;

            }

            case 3:{

                three.push(b);

                break;

            }

            case 4:{

                four.push(b);

                break;

            }

            case 5:{

                five.push(b);

                break;

            }

            case 6:{

                six.push(b);

                break;

            }

            case 7:{

                seven.push(b);

                break;

            }

            case 8:{

                eight.push(b);

                break;

            }

            case 9:{

                nine.push(b);

                break;

            }

        }

    }

    int mid=n/10;

    long long res=0;

    while(zero.size()>mid){

        res+=zero.top();

        zero.pop();

    }

    while(one.size()>mid){

        res+=one.top();

        one.pop();

    }

    while(two.size()>mid){

        res+=two.top();

        two.pop();

    }

    while(three.size()>mid){

        res+=three.top();

        three.pop();

    }

    while(four.size()>mid){

        res+=four.top();

        four.pop();

    }

    while(five.size()>mid){

        res+=five.top();

        five.pop();

    }

    while(six.size()>mid){

        res+=six.top();

        six.pop();

    }

    while(seven.size()>mid){

        res+=seven.top();

        seven.pop();

    }

    while(eight.size()>mid){

        res+=eight.top();

        eight.pop();

    }

    while(nine.size()>mid){

        res+=nine.top();

        nine.pop();

    }

    cout<<res;

    return 0;

}
```

map嵌套priority\_queue

```cpp
#include<bits/stdc++.h>

using namespace std;

map<int,priority_queue<int,vector<int>,greater<int>>> pqmap;

int main()

{

    int n;cin>>n;

    for(int i=0;i<n;i++){

        int a,b;cin>>a>>b;

        pqmap[a].push(b);

    }

    int mid=n/10;

    long long res=0;

    for(auto &entry:pqmap){

        auto &pq=entry.second;

        while(pq.size()>mid){

            res+=pq.top();

            pq.pop();

        }

    }

    cout<<res;

    return 0;

}
```

虽然但是 上面代码766ms 下面889ms （bushi）

## 同类题型

## 视频讲解

---
⬅️ [[付账问题|付账问题]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/中位 平均/最小的和|最小的和]]